CSPS2021-1 题解

题目大意

题目传送门

m1m_1 个 A 类区间,m2m_2 个 B 类区间,以及 nn。找到一组合法解 a1,a2a_1,a_2 满足 a1+a2=na_1+a_2=n,使得令 A 类区间不超过 a1a_1 个有共同子区间、B 类区间有不超过 a2a_2 个有共同子区间,所需删除区间尽量小。设最小删除区间数为 kk,输出 m1+m2km_1+m_2-k。保证所有区间左右端点互不相同,n,m1+m2105n,m_1+m_2\leqslant 10^5

本博客包含一个错解和两个正解。

考场解法(错解)

考虑一组最优解 a1,a2a_1,a_2,如果减小 a1a_1 的值,A 类区间就要删除更多的区间,B 类区间会减少需要删除的区间。但是因为 a1,a2a_1,a_2 已经是最优解了,B 类区间减少的要删除的区间数量不大于 A 类区间要增加的区间数量。

因此推测最后的答案呈单峰性质。考虑三分查找找到峰值。

现在的问题就是我已经确定了 a1,a2a_1,a_2,如何用一个可以接受的复杂度去求解需要删除多少个区间。不难看出,如果按照区间的左端点排个序,显然可以按照顺序,加进一个区间时,如果区间左端点上没有被至少 aia_i 个区间覆盖,就加进去,否则删掉这个区间。用线段树维护区间的覆盖情况。

复杂度 O(nlog32log2n)\operatorname{O}(n\log_{\frac{3}{2}}\log_2 n)

错误的原因是,可以证明这并不是单峰的。

改题解法(正解)

既然并不是单峰的,那不就可以模拟退火吗?

朴素的贪心算法,我们找到一个点,每次贪心地走左边或者右边,如果当前这个点的函数值(即答案)更小就走这边。显然这是错误的,我们会卡死在一个局部最优的情况。这个贪心显然被假掉的原因就在于我们被拘束在一个局部凸包里面,无法跳出去。如果我们给一个概率使它可以跳出去呢?

这就是模拟退火有一定概率得到正确答案的原因。确切地说,考虑模拟物理降温的过程:

  • 设定一个当前温度 TT
  • 设定每次温度的变化比 ΔT\Delta T
  • 每次退火,找到一个向左的位置和向右的位置,求其函数值 f(x),f(y)\operatorname{f}(x),\operatorname{f}(y)
  • 如果一端比当前状态小的话,贪心地跳过去。
  • 如果比当前状态大,我们有一定的概率跳过去。
  • 温度降到一定值以下截止。

找到的向左的位置和向右的位置、以及跳上去的概率不能乱定。原则上,越到后面,我们会越趋近于正解,所以应该逐渐稳定下来。根据热力学物理学家们的研究,增量的概率最好为 exp(xT)\exp(\frac{x}{T}),其中 xx 是当前解与当前目标解之差。

本着越来越稳定的原则,温度越低波动应该越小,因此一般以 T×k×randT\times k\times rand 为左右发展长度,其中 kk 是根据题目不同自行设定的,一般直接设为 nnrandrand 是属于区间 (0,1](0,1] 的实数。

在本题中,因为洛谷数据较水,并不需要特别在意跳到劣解的概率,写好波动范围即可。

冥间数据 AC 代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m1,m2,q1[max_n*4],q2[max_n*4];
struct plane{
    int l,r;
    inline void init(int x,int y){
        l=x,r=y;
    }
}a[max_n],b[max_n];
inline bool cmp(plane a,plane b){
    return a.l<b.l;
}

int lisan[max_n*4],cntls;

int ans,nowans,R1,R2;

int In[max_n],a1[max_n*4],a2[max_n*4],ar[max_n],br[max_n];

inline int check(int in){ // O(n) 判断多少个飞机停桥
	if(In[in]) return In[in];
	int out=n-in,res=0,tmp=0;
	for(register int i=1;i<=R1;++i)
		a1[i]=q1[i];
	for(register int i=1;i<=R2;++i)
		a2[i]=q2[i];
	for(register int i=1;i<=R1;++i){
		if(a1[i]==1 && tmp<in)
			++res;
		else if(a1[i]==1) // 满员了,删除这个飞机的信息
			a1[i]=a1[ar[i]]=0;
		tmp+=a1[i];
	}
	tmp=0;
	for(register int i=1;i<=R2;++i){ // 国际航班同理
		if(a2[i]==1 && tmp<out)
			++res;
		else if(a2[i]==1)
			a2[i]=a2[br[i]]=0;
		tmp+=a2[i];
	}
	return In[in]=res;
}

int As[max_n];
const int tim=1;
const double tem=0.98,delta=0.98,eps=0.0001;

inline void findans(){ // 模拟退火
	int anss=ans,nowanss=nowans;
	double nowt=tem;
	while(nowt>eps){
		int len=1.0*nowt*n*rand()/RAND_MAX,L=nowanss-len,R=nowanss+len;
		if(L>=0){
			int tmp=check(L);
			if(tmp>anss){
				anss=tmp,
				nowanss=L;
				if(ans<anss){
					ans=anss,
					nowans=nowanss;
				}
			}
		}
		if(R<=n){
			int tmp=check(R);
			if(tmp>anss){
				anss=tmp,
				nowanss=R;
				if(ans<anss){
					ans=anss,
					nowans=nowanss;
				}
			}
		}
		nowt*=delta;
	}
	if(ans<anss){
		ans=anss,
		nowans=nowanss;
	}
}

signed main(){
	freopen("airport.in","r",stdin),
	freopen("airport.out","w",stdout);
    n=read(),m1=read(),m2=read();
    for(register int i=1;i<=m1;++i){
        int l=read(),r=read();
        a[i].init(l,r);
        lisan[++cntls]=l,
        lisan[++cntls]=r;
    }
    sort(lisan+1,lisan+1+cntls),R1=cntls; // 离散化
    for(register int i=1;i<=m1;++i){
        a[i].l=lower_bound(lisan+1,lisan+1+cntls,a[i].l)-lisan;
        a[i].r=lower_bound(lisan+1,lisan+1+cntls,a[i].r)-lisan;
        q1[a[i].l]=1,q1[a[i].r]=-1;
        ar[a[i].l]=a[i].r;
    }
    cntls=0;
    for(register int i=1;i<=m2;++i){
        int l=read(),r=read();
        b[i].init(l,r);
        lisan[++cntls]=l,
        lisan[++cntls]=r;
    }
    sort(lisan+1,lisan+1+cntls),R2=cntls;
    for(register int i=1;i<=m2;++i){
        b[i].l=lower_bound(lisan+1,lisan+1+cntls,b[i].l)-lisan;
        b[i].r=lower_bound(lisan+1,lisan+1+cntls,b[i].r)-lisan;
        q2[b[i].l]=1,q2[b[i].r]=-1;
        br[b[i].l]=b[i].r;
    }

    sort(a+1,a+1+m1,cmp), // 记得排序
    sort(b+1,b+1+m2,cmp);

	ans=check(n/2),nowans=n/2;
	for(register int i=1;i<=tim;++i)
		findans();
    write(ans);
    return 0;
}